<?php
/**
 * 典型的常见排序类：
 * 冒泡排序
 * 插入排序
 * 快速排序
 * 木桶排序
 * 等
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbSortInterface;

class ClassicSort implements XxbSortInterface
{
    const SORT_TYPE_ASC = 1; // 升序排序
    const SORT_TYPE_DESC = 2; // 降序排序

    private $sortType;

    /**
     * @var array $data
     */
    private $data;

    /**
     * @param $sortType
     */
    public function setSortType($sortType)
    {
        if ($sortType != self::SORT_TYPE_ASC && $sortType != self::SORT_TYPE_DESC) {
            throw new \InvalidArgumentException('sort type invalid');
        }
        $this->sortType = $sortType;
    }

    /**
     * ClassicSort constructor.
     *
     * @param     $data
     * @param int $sortType
     */
    public function __construct($data, $sortType = self::SORT_TYPE_ASC)
    {
        if (!is_array($data)) {
            throw new \TypeError('sort data must be array');
        }
        if (empty($data)) {
            throw new \RuntimeException('data cannot be empty');
        }

        $this->data = $data;
        $this->sortType = $sortType;
    }

    public function quick()
    {
        return $this->quickOrderTarget(0, count($this->data) - 1);
    }

    public function bucket()
    {
        $min = min($this->data);
        $max = max($this->data);
        // 创建木桶
        $bucket = array_fill($min, $max - $min + 1, 0);
        // 记录原数据出现次数
        foreach ($this->data as $val) {
            $bucket[$val]++;
        }
        $result = [];
        // 根据木桶中的记录的映射生成排序数据
        if ($this->sortType === self::SORT_TYPE_ASC) {
            foreach ($bucket as $k => $val) {
                for ($i=0; $i<$val; $i++) {
                    $result[] = $k;
                }
            }
        } else {
            for ($i=$max; $i>=$min; $i--) {
                for ($j=0; $j<$bucket[$i]; $j++) {
                    $result[] = $i;
                }
            }
        }

        return $result;
    }

    public function insert()
    {
        // TODO: Implement insert() method.
    }

    public function forwardBubble()
    {
        for ($i=1, $n=count($this->data); $i<$n; $i++) {
            for ($j=$i, $minIndex=$i-1; $j<$n; $j++) {
                if ($this->data[$j] < $this->data[$minIndex]) {
                    $minIndex = $j;
                }
            }
            if ($minIndex != $i-1) {
                $temp = $this->data[$minIndex];
                $this->data[$minIndex] = $this->data[$i-1];
                $this->data[$i-1] = $temp;
            }
        }
        return $this->data;
    }

    /**
     * 反向冒泡排序：
     * 思路就是从待排序序列中取出最小值/最大值，取出n-1次最小值/最大值，则序列排序完成
     * 通过内外循环实现，外循环控制取几次最小值/最大值，内循环实现取出待排序序列的最小值/最大值
     *
     * @return mixed
     */
    public function reversedBubble()
    {
        $exp = sprintf(
            'if ($data[$j] %s $data[$index]) $index = $j;',
            $this->sortType == self::SORT_TYPE_ASC ? '<' : '>'
        );

        for ($i=1,$n=count($this->data); $i<$n; $i++) {
            for ($j=$n-1, $index=$i-1; $j>=$i; $j--) {
                eval($exp);
            }
            if ($index != $i-1) {
                $temp = $this->data[$index];
                $this->data[$index] = $this->data[$i-1];
                $this->data[$i-1] = $temp;
            }
        }
        return $this->data;
    }

    /**
     * 二分法排序目标
     * @param $start
     * @param $end
     *
     * @return array
     */
    private function quickOrderTarget($start, $end)
    {
        $middleValIndex = $this->divideTarget($start, $end);
        if ($start < $end) {
            $this->quickOrderTarget($start, $middleValIndex - 1);
            $this->quickOrderTarget($middleValIndex + 1, $end);
        }
        return $this->data;
    }

    /**
     * 根据中间值划分目标
     * @param $start
     * @param $end
     *
     * @return int|mixed
     */
    private function divideTarget($start, $end)
    {
        if ($start >= $end) {
            return $start;
        }
        // 三数取中法，先确定一个最大值，并放到end位置上
        // 注意这里要+start否则中间位置可能不在start和end范围内
        $middleIndex = ceil(($end - $start) / 2) + $start;
        if ($this->data[$start] > $this->data[$end]) {
            $temp = $this->data[$start];
            $this->data[$start] = $this->data[$end];
            $this->data[$end] = $temp;
        }
        if ($this->data[$middleIndex] > $this->data[$end]) {
            $temp = $this->data[$middleIndex];
            $this->data[$middleIndex] = $this->data[$end];
            $this->data[$end] = $temp;
        }
        // 把中间值放到start位置上
        if ($this->data[$middleIndex] > $this->data[$start]) {
            $temp = $this->data[$middleIndex];
            $this->data[$middleIndex] = $this->data[$start];
            $this->data[$start] = $temp;
        }
        $middleVal = $this->data[$start];

        // 根据中间值划分目标
        while ($start < $end) {
            if ($this->sortType == self::SORT_TYPE_ASC) {
                // 比中间值大的放在end这边 比中间值小的放在start这边
                while ($start < $end && $this->data[$end] >= $middleVal) {
                    $end--;
                }
                $start < $end && $this->data[$start] = $this->data[$end];
                while($start < $end && $this->data[$start] <= $middleVal) {
                    $start++;
                }
                $start < $end && $this->data[$end] = $this->data[$start];
            } else {
                // 比中间值大的放在start这边 比中间值小的放在end这边
                while ($start < $end && $this->data[$end] <= $middleVal) {
                    $end--;
                }
                $start < $end && $this->data[$start] = $this->data[$end];
                while($start < $end && $this->data[$start] > $middleVal) {
                    $start++;
                }
                $start < $end && $this->data[$end] = $this->data[$start];
            }
        }

        $this->data[$start] = $middleVal;
        return $start;
    }
}
